package com.wjy.Data_Structure.divide;

public class divide {
	public class IntPair {
		int max;
		int min;
	}

	/**
	 * @param a 输入：整数数组 a[0, n-1] 
	 * @return  输出：a 中的大与小元素 
	 */
	public IntPair simpleMinMax(int[] a) {
		IntPair pair = new IntPair();
		pair.max = a[0];
		pair.min = a[0];
		for (int i = 1; i < a.length; i++) {
			if (pair.max < a[i])
				pair.max = a[i];
			if (pair.min > a[i])
				pair.min = a[i];
		}
		return pair;
	}

	/**
	 * 使用分治法
	 * @param a
	 * @param low
	 * @param high
	 * @return
	 */
	public IntPair min_max(int[] a, int low, int high) {
		IntPair pair = new IntPair();
		if (low <= high - 2) {
			int mid = (low + high) / 2;
			IntPair p1 = min_max(a, low, mid);
			IntPair p2 = min_max(a, mid + 1, high);
			pair.max = p1.max > p2.max ? p1.max : p2.max;
			pair.min = p1.min < p2.min ? p1.min : p2.min;
		} else {
			//			if (a[low] < a[high]) {
			//				pair.max = a[high];
			//				pair.min = a[low];
			//			} else {
			//				pair.min = a[high];
			//				pair.max = a[low];
			//			}
			pair.max = a[low] < a[high] ? a[high] : a[low];
			pair.min = a[low] < a[high] ? a[low] : a[high];
		}
		return pair;
	}

}
